package 二叉树.中序遍历.栈方法;


import java.util.ArrayList;
import java.util.Stack;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {


    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.left=node2;
        node2.right=node3;
        int[] ints = inorderTraversal(node1);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }
    public static int[] inorderTraversal(TreeNode root) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return new int[]{};
        }
        // 让p指针指向根节点
        TreeNode p = root;
        // 若栈不为空 或者 p 指针不为空
        while (!stack.isEmpty() || p != null) {
            // 若该结点 不为null, 则入栈, 并且让指针指向该结点的 左孩子结点
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                // 若该该结为null; 那么将该结点出栈.  并且 让指针指向栈顶右孩子结点
                TreeNode pop = stack.pop();
                list.add(pop.val);
                p = pop.right;
            }
        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i);
        }
        return ints;


    }


}
